﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

public class Solution41
{
    public int FirstMissingPositive1(int[] nums)//傻逼方法
    {
        int min = 1;

        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] == min+1)
            {
                min = nums[i];
            }

        }
        return min+1;

    }
    //把数组改造成一个可以标记的hash表
    //这个整数的范围是（0，N+1)
    public int FirstMissingPositive(int[] nums)
    {
        
        int len=nums.Length;

        //先把负数都变成正数，反正也不需要
        for (int i = 0; i < nums.Length; i++)
        {
            if (nums[i] <=0)
            {
                 nums[i]=len+1;
            }

        }
        //遇到的数，在对应的index标记为负数
        for (int i = 0; i < nums.Length; i++)
        {
            int index = 0;
            if (nums[i] > 0)
            {
                index = nums[i];
                
            }
            else//小于0的说明标记过了
            {
                 index = -nums[i];
               
            }

            if(index <= len)//不越界
            {

                // nums[index-1]有没有可能为负数，有可能，因为数组里面可能有重复的，标记过的不要再标记了
                //nums[index-1] = -nums[index-1];//index-1是为了利用上nums【0】，因为数组没有0，所以nums【0】浪费

                if(nums[index - 1] > 0)
                {
                    nums[index - 1] = -nums[index - 1];
                }



            }
        }
        for (int i = 0; i < nums.Length; i++)
        {
            
            if (nums[i] > 0)
            {
                return i + 1;//第一个整数，说明这个index对应的数字不存在

            }
          
        }

        //如果全部负数，说明整数都在，最小未存在的为N+1
        return len+1;

    }
}

class Program41
{
    static void Main41(string[] args)
    {
        Solution41 solution = new Solution41();
        int[] nums = [1, 2, 0];
        int res= solution.FirstMissingPositive(nums);
        Console.WriteLine(res);

    }
}
